package com.datastructure.test.arabictoroman;

import java.util.LinkedHashMap;
import java.util.Map;

public class ArabicToRoman {
    public static void main(String[] args) {
        ArabicToRoman arabicToRoman = new ArabicToRoman();
        String roman = arabicToRoman.ArabicToRoman(5);
        System.out.println(roman);
    }

    boolean flag = false;
    public String ArabicToRoman (int n) {
        // write code here
//        Map<Integer,Node> map = new LinkedHashMap<>();
//        map.put(0,new Node("I",1));
//        map.put(1,new Node("V",5));
//        map.put(2,new Node("X",10));
//        map.put(3,new Node("L",50));
//        map.put(4,new Node("C",100));
//        map.put(5,new Node("D",500));
//        map.put(6,new Node("M",1000));
//        map.put(7,new Node("T",5000));
//        StringBuilder stringBuilder = new StringBuilder();
//        dfs(map, n, stringBuilder);
//        String replace = stringBuilder.toString().replace("xxxx", "XL");
//        String s = replace.replace("DCCCCLXL", "CMXC");
//        return s;
        // 这里使用StringBuilder保存转换后的罗马数， 注意：这里有一个java面试的考点：Java中String、StringBuilder以及StringBuffer的比较
        StringBuilder res = new StringBuilder();
        // 用数组保存整数区间及其对应的罗马数区间
        int[] n1 = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] str = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        for(int i=0; i<n1.length; i++){
            // 判断该整数属于哪一个区间
            while(n >= n1[i]){
                // 找到区间数后，计算剩余数
                n -= n1[i];
                // 添加区间数对应的罗马数
                res.append(str[i]);
            }
        }

        return res.toString();
    }


    private void dfs(Map<Integer, Node> map, int n, StringBuilder stringBuilder) {
        if(n==4){
            stringBuilder.append("IV");
            flag=true;
        } else if(n==9) {
            stringBuilder.append("IX");
            flag=true;
        }else if(n==40) {
            stringBuilder.append("XL");
            flag=true;
        }else if(n==90) {
            stringBuilder.append("XC");
            flag=true;
        }else if(n==400) {
            stringBuilder.append("CD");
            flag=true;
        }else if(n==900) {
            stringBuilder.append("CM");
            flag=true;
        }
        for (int i = 0; i < map.size(); i++) {
            Node node = map.get(i);
            if(node.value>=n){
                if(node.value==n){
                    if(!flag){
                        stringBuilder.append(node.key);
                        flag=true;
                    }
                }else {
                    if(n<5){
                        if(!flag){
                            for(int k=0;k<n;k++){
                                stringBuilder.append("I");
                            }
                            flag=true;
                        }
                    } else {
                        if(!flag){
                            stringBuilder.append(map.get(i - 1).key);
                            dfs(map, n - map.get(i - 1).value, stringBuilder);
                        }
                    }
                }
            }
        }
    }
}

class Node{
    public String key;
    public int value;

    public Node(String key, int value) {
        this.key = key;
        this.value = value;
    }
}
